#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "SelectionSort.h"
#include "InsertionSort.h"
#include "BubbleSort.h"
#include "MergeSort.h"
#include "HeapSort.h"
#include "QuickSort.h"

#include "my_lib.h"
#include "my_limits.h"


static void (*Sorting_func[8])(int*, int) = {
	Selection_sort,
	Insertion_sort_lin,
	Insertion_sort_bin,
	Bubble_sort,
	Merge_sort,
	Heap_sort,
	Quick_sort,
	Quick_sort_rand
};

static char *Sorting_f_name[8] = {
	"Selection sort",
	"Insertion sort",
	"Insertion sort (with binary insertions)",
	"Bubble sort",
	"Merge sort",
	"Heap sort",
	"Quick sort",
	"Quick sort (with pivot randomisation)"
};



static int
check_sorted_array(int* array, int a_size)
{
	register int i = 1;
	while (i<a_size)
		if (array[i-1] > array[i])
			return 1;
		else
			++i;
	return 0;
}



int
main(int argc, char **argv)
{
	static int	sequence[SEQ_MAXLEN];
	int		a_size = (int)1E+5;
	register int	i, j, r;
	static clock_t	my_timer_tmp;
	static clock_t	my_timer[6][3][8];
	static char	line[LINE_MAXLEN+1];
	static char	text_table[LINES_MAXCOUNT][LINE_MAXLEN+1];
	static int	lineN = 0;

	printf("\"Header\",\"Sorting algorithm\",\"Time on sorted array\",\
\"Time on reverse-sorted array\",\"Avg time on 10 randomized arrays\"\n");
	sprintf(text_table[lineN++],
			" | Sorting algorithm | Time on sorted array | \
Time on reverse-sorted array | Avg time on 10 randomized arrays");
	for (i = 0 ; a_size <= SEQ_MAXLEN ; ++i, a_size *= 10) {
		fprintf(stderr, "\n N == %d\n", a_size);

		putchar('\n');
		printf(",\"N == %d\"\n", a_size);
		sprintf(text_table[lineN++], " | N == %d | | | ", a_size);

		for (j = 0 ; j < 8 ; ++j) { /* 8 == amount of funcs */
			/*
			 * We'll use CSV format, since it's pretty easy
			 * to implement and LibreOffice Calc supports it.
			 */
			printf("%d,\"%s\",", j+1, Sorting_f_name[j]);
			(void)fflush(NULL);

			/*
			 * Disallow simple sorting algorithms to run on
			 *   huge arrays
			 */
			if (a_size > (int)1E+5 && j <= 3) {
				printf("\"skipped\",\"skipped\",\"skipped\"\n");
				continue;
			}
			if (a_size > (int)1E+6 && j == 6) {
				printf("\"skipped\",\"skipped\",");
				goto test_random_seq;
			}

			/*
			 * Sorted array
			 */
			gen_sorted(sequence, a_size);

			my_timer_tmp = clock();
			Sorting_func[j](sequence, a_size);
			my_timer[i][0][j] = clock() - my_timer_tmp;
			if (check_sorted_array(sequence, a_size)) {
				fprintf(stderr, "Bad sort! (%s)\n", Sorting_f_name[j]);
			}
			(void) printf("%g,", (double)my_timer[i][0][j] / CLOCKS_PER_SEC);
			(void) fflush(NULL);

			/*
			 * Reverse-sorted array
			 */
			gen_rev_sorted(sequence, a_size);

			my_timer_tmp = clock();
			Sorting_func[j](sequence, a_size);
			my_timer[i][1][j] = clock() - my_timer_tmp;
			if (check_sorted_array(sequence, a_size)) {
				fprintf(stderr, "Bad sort! (%s)\n", Sorting_f_name[j]);
			}
			(void)printf("%g,", (double)my_timer[i][1][j] / CLOCKS_PER_SEC);
			(void)fflush(NULL);

			/*
			 * Randomised array
			 */
test_random_seq:
			my_timer[i][2][j] = 0; /* initialize value */
			for (r = 0 ; r < RANDOM_TRUST_LIMIT ; ++r) {
				/*
				 * We have to generate it every time
				 */
				gen_rand(sequence, a_size);

				/*
				 * Run sort
				 */
				my_timer_tmp = clock();
				Sorting_func[j](sequence, a_size);
				my_timer[i][2][j] += clock() - my_timer_tmp;
				if (check_sorted_array(sequence, a_size)) {
					fprintf(stderr, "Bad sort! (%s)\n", Sorting_f_name[j]);
				}
			}
			printf("%g\n",
			       ((double)my_timer[i][2][j] / RANDOM_TRUST_LIMIT) / CLOCKS_PER_SEC);
			sprintf(text_table[lineN++],
					"%3d | %45s | %5.3lf | %5.3lf | %5.3lf",
					i, Sorting_f_name[j], my_timer[i][0][j],
					my_timer[i][1][j],
					((double)my_timer[i][2][j] / RANDOM_TRUST_LIMIT) / CLOCKS_PER_SEC);
		}
	}

	/*
	 * Wouldn't it be cool to implement a cool algorithm
	 *   that draws a really nice and readable table,
	 *   instead of that 80'ish CSV format?..
	 */
	i=0;
	while(i<lineN)
		puts(text_table[i++]);
	return 0;
}
